package Solutions

func numRollsToTarget(n int, k int, target int) int {
    if target<n||target>n*k{
        return 0
    }
    var dp=make([][]int,n+1)
    for i:=range dp{
        dp[i]=make([]int,target+1)
    }
    for i:=1;i<=k&&i<=target;i++{
        dp[1][i]=1
    }
    
    for i:=2;i<=n;i++{
        maxT:=min__1150(i*k,target)
        for j:=1;j<=maxT;j++{
            for m:=1;m<=k&&m<j&&m<target;m++{
                dp[i][j]=(dp[i-1][j-m]+dp[i][j])%(1000000000+7)
            } 
        }
    }
    return (dp[len(dp)-1][len(dp[0])-1])
}
func min__1150(i,j int)int{
    if i<j{
        return i
    }
    return j
}